#include "headfiles.h"

using namespace std;

vector<vector<int> > subsets(vector<int> &S) {
    vector<vector<int>> output;
    vector<int> elem_loc;
    output.push_back(vector<int>());
    if (S.empty()) {
        return output;
    }
    
    int i; 
    for (i = 0; i < S.size(); i++) {
        output.push_back(vector<int>(S[i]));
        elem_loc.push_back(i);
    }
    
    auto it = output.begin();
    auto lit = elem_loc.begin();
    it++;
    while (it != output.end()) {
        int loc = *lit + 1;
        for (; loc < S.size(); loc++) {
            vector<int> tmp = *it;
            tmp.push_back(S[loc]);
            elem_loc.push_back(loc);
            output.push_back(tmp);
        }
        
        lit++;
        it++;
    }

    return output;
}
